package com.yiwenup.leetcode.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 **/
public class No062 {
    /**
     * 执行用时：1334 ms, 在所有 Java 提交中击败了5.04%的用户
     * 内存消耗：40.7 MB, 在所有 Java 提交中击败了6.44%的用户
     */
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        int size = list.size();
        int offset = m - 1;
        while (size > 1) {
            idx = (idx + offset) % (size--);
            list.remove(idx);
        }
        return list.get(0);
    }

    /**
     * 执行用时：4 ms, 在所有 Java 提交中击败了99.99%的用户
     * 内存消耗：35.2 MB, 在所有 Java 提交中击败了78.27%的用户
     * TODO
     */
    public int lastRemaining2(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}
